class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for i in range(len(s)):
            if s[i] == '[':
                t = i - 1
                while s[t].isdigit():
                    num = int(s[t:i])
                    t -= 1
                stack.append([i, num, t])  # 左括号， 次数，t为起始位置
            elif s[i] == ']':
                j, num, t = stack.pop()
                return self.decodeString(s[:t + 1] + num * s[j + 1:i] + s[i + 1:])
        return s


if __name__ == '__main__':
    s = Solution()
    r = s.decodeString("2[abc]3[cd]ef")
    print(r)
